package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeLevelOrderTraversalII {

	public static void main(String[] args) {
	}
	
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	Stack<List<Integer>> res = new Stack<List<Integer>>();
    	if (root == null) return res;
    	
    	Queue<TreeNode> q = new LinkedList<TreeNode>();
    	q.add(root);
    	
    	while (!q.isEmpty()) {
    		int size = q.size();
    		List<Integer> temp = new ArrayList<Integer>();
    		
    		for (int i = 0; i < size; i++) {
    			TreeNode t = q.poll();
    			temp.add(t.val);
    			
    			if (t.left != null) q.add(t.left);
    			if (t.right != null) q.add(t.right);
    		}
    		res.add(temp);
    	}
    	
    	List<List<Integer>> finalRes = new LinkedList<List<Integer>>();
    	
    	// Not interesting, just reverse the order
    	while (!res.isEmpty()) {
    		finalRes.add(res.pop());
    	}
    	
    	return finalRes;
    }

}
